#!/usr/bin/python

class LeastRecentlyUsed(dict):
	"""
	>>> l=LeastRecentlyUsed(3)
	>>> l[1]=1
	>>> l[2]=2
	>>> l[3]=3
	>>> l
	{1: 1, 2: 2, 3: 3}
	
	Here, 1 should get ejected
	>>> l[4]=4
	>>> l
	{2: 2, 3: 3, 4: 4}
	
	Touch 2 such that it won't be ejected next, 3 then becomes the oldest
	>>> foo=l[2]
	>>> l[5]=5
	>>> l
	{2: 2, 4: 4, 5: 5}
	"""
	def __init__(me,size_limit):
		dict.__init__(me)
		me.size_limit=size_limit
		me.t=1
		me.timestamps={}
		
	def __getitem__(me,k):
		val=dict.__getitem__(me,k)
		me.timestamps[k]=me.t
		me.t+=1
		return val
		
	def __setitem__(me,k,val):
		dict.__setitem__(me,k,val)
		me.timestamps[k]=me.t
		me.t+=1
		if len(me)>me.size_limit:
			me._eject_oldest()
			
	def _eject_oldest(me):
		k_oldest=None
		t_oldest=None
		for k in me:
			t=me.timestamps[k]
			if not t_oldest or t_oldest > t:
				t_oldest=t
				k_oldest=k
		assert t_oldest
		del me[k_oldest]
		del me.timestamps[k_oldest]
		assert len(me)==me.size_limit
		
if __name__=="__main__":
	import doctest
	doctest.testmod()